﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using ClusterAggregation.Datum;
using ClusterAggregation.DataSets;

namespace ClusterAggregation.Clusterers
{
	/**
	 * based uppon the work of Edward Raff (from java code GPL v3)
	 * http://code.google.com/p/java-statistical-analysis-tool
	 */
	public class CPamImpl:IClusterer
	{
		/** distance function */
		protected ISimilarity m_distFunc;
		/** random number generator */
		protected Random m_randomGenerator;
		/** number of repeats */
		protected int m_repeats = 1;
		/** maximum iterations */
		protected int m_iterLimit = 100;

		/**
		 * basic constructor
		 * @param dm (ISimilarity) [IN] distance metric
		 * @param rand (Random) [IN] Random number generator
		 * @param seedSelection (SeedSelectionMethods.SeedSelection) [IN] Seed Selection
		 */
		public CPamImpl(ISimilarity dm = null, Random rand = null)
		{
			this.m_distFunc = dm;
			if (dm == null)
				this.m_distFunc = new CEuclideanDistanceSimilarityFunction();
			this.m_randomGenerator = rand;
			if (rand == null)
				this.m_randomGenerator = new Random();
		}
	
		/**
		 * Performs the actual work of PAM. 
		 * 
		 * @param data the data set to apply PAM to
		 * @param medioids the array to store the indices that get chosen as the medoids. The length of the array indicates how many medoids should be obtained. 
		 * @param assignments an array of the same length as <tt>data</tt>, each value indicating what cluster that point belongs to. 
		 * @return the sum of the squared distance from each point to its closest medoid 
		 */
		public CPartition cluster(AData[] data, ISimilarity dm,  int numOfClusters)
		{
			CPartition res = new CPartition();
			res.name = "PAM";
			int[] assignments = new int[data.Length];
			int[] medioids = new int[numOfClusters];
			double totalDistance = 0;
			int changes = -1;
			for (int i = 0; i < assignments.Length; i++)
			{
				assignments[i] = -1;
			}//-1, invalid category!
			for (int i = 0; i < numOfClusters; i++)
			{
				res.clusters.Add(new CCluster());
			}
			int[] bestMedCand = new int[medioids.Length];
			double[] bestMedCandDist = new double[medioids.Length];            

			int iter = 0;
			do
			{
				changes = 0;
				totalDistance = 0.0;

				for (int i = 0; i < data.Length; i++)
				{                    
					int assignment = 0;
					double minDist = dm.similarity(data[medioids[0]], data[i]);

					for (int k = 1; k < medioids.Length; k++)
					{
						double dist = dm.similarity(data[medioids[k]], data[i]);
						if (dist < minDist)
						{
							minDist = dist;
							assignment = k;
						}
					}

					//Update which cluster it is in
					if (assignments[i] != assignment)
					{
						changes++;
						assignments[i] = assignment;                        
					}
					totalDistance += minDist * minDist;

				}


				//Update the medioids               
				for (int i = 0; i < bestMedCandDist.Length; i++)
				{
					bestMedCandDist[i] = double.MaxValue;
				}
				for (int i = 0; i < data.Length; i++)
				{
					double thisCandidateDistance = 0.0;
					int clusterID = assignments[i];                   
					for (int j = 0; j < data.Length; j++)
					{
						if (j == i || assignments[j] != clusterID)
							continue;
						thisCandidateDistance += Math.Pow(dm.similarity(data[i], data[j]), 2);
					}

					if (thisCandidateDistance < bestMedCandDist[clusterID])
					{
						bestMedCand[clusterID] = i;
						bestMedCandDist[clusterID] = thisCandidateDistance;
					}
				}
				for (int i = 0; i < medioids.Length; i++)
				{
						medioids[i] = bestMedCand[i];
				}                
			}
			while (changes > 0 && iter++ < m_iterLimit);

			for (int i = 0; i < data.Length; i++)
			{
				res.clusters[assignments[i]].data.Add(data[i]);
			}
			return res;
		}
	}
}

